<html>
<head><meta charset="utf-8"><title>BTreeMap &quot;highest key below&quot; and ranges &quot;containing&quot; a key? · t-libs · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/index.html">t-libs</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.20.22highest.20key.20below.22.20and.20ranges.20.22containing.22.20a.20key.3F.html">BTreeMap &quot;highest key below&quot; and ranges &quot;containing&quot; a key?</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="190838468"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%20%22highest%20key%20below%22%20and%20ranges%20%22containing%22%20a%20key%3F/near/190838468" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.20.22highest.20key.20below.22.20and.20ranges.20.22containing.22.20a.20key.3F.html#190838468">(Mar 17 2020 at 12:14)</a>:</h4>
<p>I'm interested in having a function in <code>BTreeMap</code> that would return the highest key below a given key, and a function that returns a range where the lower bound is expanded to include the next key below. (This would be for a BTreeMap representing ranges/extents of data.) Does that seem like a reasonable thing to do?</p>



<a name="190838527"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%20%22highest%20key%20below%22%20and%20ranges%20%22containing%22%20a%20key%3F/near/190838527" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.20.22highest.20key.20below.22.20and.20ranges.20.22containing.22.20a.20key.3F.html#190838527">(Mar 17 2020 at 12:15)</a>:</h4>
<p><code>some_btreemap.highest_key_below(k)</code> is equivalent to <code>some_btreemap.range(..=k).next_back().map(|(k, _)| k)</code></p>



<a name="190838666"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%20%22highest%20key%20below%22%20and%20ranges%20%22containing%22%20a%20key%3F/near/190838666" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.20.22highest.20key.20below.22.20and.20ranges.20.22containing.22.20a.20key.3F.html#190838666">(Mar 17 2020 at 12:16)</a>:</h4>
<p>And then the range function I'm looking for would be equivalent to <code>some_btreemap.range(some_btreemap.highest_key_below(start)..end)</code>, but only walking the tree once, not twice.</p>



<a name="190838746"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%20%22highest%20key%20below%22%20and%20ranges%20%22containing%22%20a%20key%3F/near/190838746" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Amanieu <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.20.22highest.20key.20below.22.20and.20ranges.20.22containing.22.20a.20key.3F.html#190838746">(Mar 17 2020 at 12:17)</a>:</h4>
<p>Can't you already do this with <code>range</code>?</p>



<a name="190838820"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%20%22highest%20key%20below%22%20and%20ranges%20%22containing%22%20a%20key%3F/near/190838820" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Amanieu <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.20.22highest.20key.20below.22.20and.20ranges.20.22containing.22.20a.20key.3F.html#190838820">(Mar 17 2020 at 12:18)</a>:</h4>
<p>Using <code>Included</code> and <code>Excluded</code></p>



<a name="190838980"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%20%22highest%20key%20below%22%20and%20ranges%20%22containing%22%20a%20key%3F/near/190838980" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Amanieu <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.20.22highest.20key.20below.22.20and.20ranges.20.22containing.22.20a.20key.3F.html#190838980">(Mar 17 2020 at 12:20)</a>:</h4>
<p>Highest key below <code>k</code>: <code>btree.range((Unbounded, Excluded(&amp;k))).next_back()</code></p>



<a name="190839037"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%20%22highest%20key%20below%22%20and%20ranges%20%22containing%22%20a%20key%3F/near/190839037" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.20.22highest.20key.20below.22.20and.20ranges.20.22containing.22.20a.20key.3F.html#190839037">(Mar 17 2020 at 12:20)</a>:</h4>
<p>That's equivalent to what I just wrote above, yes.</p>



<a name="190839066"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%20%22highest%20key%20below%22%20and%20ranges%20%22containing%22%20a%20key%3F/near/190839066" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.20.22highest.20key.20below.22.20and.20ranges.20.22containing.22.20a.20key.3F.html#190839066">(Mar 17 2020 at 12:20)</a>:</h4>
<p>(Also, I'd want <code>Included</code>, not <code>Excluded</code>, which is why I wrote <code>..=</code> above.)</p>



<a name="190839116"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%20%22highest%20key%20below%22%20and%20ranges%20%22containing%22%20a%20key%3F/near/190839116" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Amanieu <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.20.22highest.20key.20below.22.20and.20ranges.20.22containing.22.20a.20key.3F.html#190839116">(Mar 17 2020 at 12:21)</a>:</h4>
<p>It might make more sense to add cursors to btree like we did with <code>LinkedList</code>.</p>



<a name="190839234"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%20%22highest%20key%20below%22%20and%20ranges%20%22containing%22%20a%20key%3F/near/190839234" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.20.22highest.20key.20below.22.20and.20ranges.20.22containing.22.20a.20key.3F.html#190839234">(Mar 17 2020 at 12:22)</a>:</h4>
<p>Potentially useful, but <code>range</code> really is close to what I want, I just need the ability to extend the range earlier to encompass the element preceding a key.</p>



<a name="190839248"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%20%22highest%20key%20below%22%20and%20ranges%20%22containing%22%20a%20key%3F/near/190839248" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.20.22highest.20key.20below.22.20and.20ranges.20.22containing.22.20a.20key.3F.html#190839248">(Mar 17 2020 at 12:22)</a>:</h4>
<p>One moment, let me post some sample code.</p>



<a name="190839314"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%20%22highest%20key%20below%22%20and%20ranges%20%22containing%22%20a%20key%3F/near/190839314" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.20.22highest.20key.20below.22.20and.20ranges.20.22containing.22.20a.20key.3F.html#190839314">(Mar 17 2020 at 12:23)</a>:</h4>
<p><a href="https://play.rust-lang.org/?version=stable&amp;mode=debug&amp;edition=2018&amp;gist=2a3adf26c8e0e0cc61fc511abab57c1c" target="_blank" title="https://play.rust-lang.org/?version=stable&amp;mode=debug&amp;edition=2018&amp;gist=2a3adf26c8e0e0cc61fc511abab57c1c">https://play.rust-lang.org/?version=stable&amp;mode=debug&amp;edition=2018&amp;gist=2a3adf26c8e0e0cc61fc511abab57c1c</a></p>



<a name="190839331"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%20%22highest%20key%20below%22%20and%20ranges%20%22containing%22%20a%20key%3F/near/190839331" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.20.22highest.20key.20below.22.20and.20ranges.20.22containing.22.20a.20key.3F.html#190839331">(Mar 17 2020 at 12:24)</a>:</h4>
<div class="codehilite"><pre><span></span><span class="k">use</span><span class="w"> </span><span class="n">std</span>::<span class="n">collections</span>::<span class="n">BTreeMap</span><span class="p">;</span><span class="w"></span>

<span class="k">fn</span> <span class="nf">main</span><span class="p">()</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="kd">let</span><span class="w"> </span><span class="k">mut</span><span class="w"> </span><span class="n">m</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">BTreeMap</span>::<span class="n">new</span><span class="p">();</span><span class="w"></span>
<span class="w">    </span><span class="n">m</span><span class="p">.</span><span class="n">insert</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span><span class="w"> </span><span class="s">&quot;data through 9&quot;</span><span class="p">);</span><span class="w"></span>
<span class="w">    </span><span class="n">m</span><span class="p">.</span><span class="n">insert</span><span class="p">(</span><span class="mi">10</span><span class="p">,</span><span class="w"> </span><span class="s">&quot;data through 99&quot;</span><span class="p">);</span><span class="w"></span>
<span class="w">    </span><span class="n">m</span><span class="p">.</span><span class="n">insert</span><span class="p">(</span><span class="mi">100</span><span class="p">,</span><span class="w"> </span><span class="s">&quot;data through 999&quot;</span><span class="p">);</span><span class="w"></span>
<span class="w">    </span><span class="n">m</span><span class="p">.</span><span class="n">insert</span><span class="p">(</span><span class="mi">1000</span><span class="p">,</span><span class="w"> </span><span class="s">&quot;data through 9999&quot;</span><span class="p">);</span><span class="w"></span>
<span class="w">    </span><span class="n">m</span><span class="p">.</span><span class="n">insert</span><span class="p">(</span><span class="mi">10000</span><span class="p">,</span><span class="w"> </span><span class="s">&quot;data through 99999&quot;</span><span class="p">);</span><span class="w"></span>

<span class="w">    </span><span class="kd">let</span><span class="w"> </span><span class="p">(</span><span class="o">&amp;</span><span class="n">first</span><span class="p">,</span><span class="w"> </span><span class="n">_</span><span class="p">)</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">m</span><span class="p">.</span><span class="n">range</span><span class="p">(..</span><span class="o">=</span><span class="mi">50</span><span class="p">).</span><span class="n">next_back</span><span class="p">().</span><span class="n">unwrap</span><span class="p">();</span><span class="w"></span>
<span class="w">    </span><span class="n">println</span><span class="o">!</span><span class="p">(</span><span class="s">&quot;first relevant key: {}&quot;</span><span class="p">,</span><span class="w"> </span><span class="n">first</span><span class="p">);</span><span class="w"></span>
<span class="w">    </span><span class="n">println</span><span class="o">!</span><span class="p">(</span><span class="s">&quot;Relevant ranges:&quot;</span><span class="p">);</span><span class="w"></span>
<span class="w">    </span><span class="k">for</span><span class="w"> </span><span class="p">(</span><span class="n">k</span><span class="p">,</span><span class="w"> </span><span class="n">v</span><span class="p">)</span><span class="w"> </span><span class="k">in</span><span class="w"> </span><span class="n">m</span><span class="p">.</span><span class="n">range</span><span class="p">(</span><span class="n">first</span><span class="p">..</span><span class="mi">5000</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">        </span><span class="n">println</span><span class="o">!</span><span class="p">(</span><span class="s">&quot;{} {}&quot;</span><span class="p">,</span><span class="w"> </span><span class="n">k</span><span class="p">,</span><span class="w"> </span><span class="n">v</span><span class="p">);</span><span class="w"></span>
<span class="w">    </span><span class="p">}</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>
</pre></div>



<a name="190839399"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%20%22highest%20key%20below%22%20and%20ranges%20%22containing%22%20a%20key%3F/near/190839399" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.20.22highest.20key.20below.22.20and.20ranges.20.22containing.22.20a.20key.3F.html#190839399">(Mar 17 2020 at 12:24)</a>:</h4>
<p>To satisfy a request for data from 50 to 5000, I need the keys 10, 100, and 1000.</p>



<a name="190839410"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%20%22highest%20key%20below%22%20and%20ranges%20%22containing%22%20a%20key%3F/near/190839410" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.20.22highest.20key.20below.22.20and.20ranges.20.22containing.22.20a.20key.3F.html#190839410">(Mar 17 2020 at 12:24)</a>:</h4>
<p>Does that make sense?</p>



<a name="190849695"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%20%22highest%20key%20below%22%20and%20ranges%20%22containing%22%20a%20key%3F/near/190849695" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Amanieu <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.20.22highest.20key.20below.22.20and.20ranges.20.22containing.22.20a.20key.3F.html#190849695">(Mar 17 2020 at 13:51)</a>:</h4>
<p>With a cursor you could do something like this:</p>
<div class="codehilite"><pre><span></span><span class="kd">let</span><span class="w"> </span><span class="k">mut</span><span class="w"> </span><span class="n">cur</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">m</span><span class="p">.</span><span class="n">cursor_at_upper_bound</span><span class="p">(</span><span class="n">Included</span><span class="p">(</span><span class="o">&amp;</span><span class="mi">50</span><span class="p">));</span><span class="w"></span>
<span class="k">while</span><span class="w"> </span><span class="kd">let</span><span class="w"> </span><span class="nb">Some</span><span class="p">((</span><span class="n">k</span><span class="p">,</span><span class="w"> </span><span class="n">v</span><span class="p">))</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">cur</span><span class="p">.</span><span class="n">get</span><span class="p">()</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="k">if</span><span class="w"> </span><span class="n">k</span><span class="w"> </span><span class="o">&gt;</span><span class="w"> </span><span class="mi">5000</span><span class="w"> </span><span class="p">{</span><span class="w"> </span><span class="k">break</span><span class="p">;</span><span class="w"> </span><span class="p">}</span><span class="w"></span>
<span class="w">    </span><span class="n">println</span><span class="o">!</span><span class="p">(</span><span class="s">&quot;{} {}&quot;</span><span class="p">,</span><span class="w"> </span><span class="n">k</span><span class="p">,</span><span class="w"> </span><span class="n">v</span><span class="p">);</span><span class="w"></span>
<span class="w">    </span><span class="n">cur</span><span class="p">.</span><span class="n">move_next</span><span class="p">();</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>
</pre></div>



<a name="191306212"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%20%22highest%20key%20below%22%20and%20ranges%20%22containing%22%20a%20key%3F/near/191306212" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.20.22highest.20key.20below.22.20and.20ranges.20.22containing.22.20a.20key.3F.html#191306212">(Mar 20 2020 at 21:41)</a>:</h4>
<p>That cursor_at_upper_bound operation would still have to exist with the semantics I described, though.</p>



<a name="191313719"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%20%22highest%20key%20below%22%20and%20ranges%20%22containing%22%20a%20key%3F/near/191313719" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Amanieu <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.20.22highest.20key.20below.22.20and.20ranges.20.22containing.22.20a.20key.3F.html#191313719">(Mar 20 2020 at 23:07)</a>:</h4>
<p><a href="https://docs.rs/intrusive-collections/0.8.5/intrusive_collections/rbtree/struct.RBTree.html#method.upper_bound" target="_blank" title="https://docs.rs/intrusive-collections/0.8.5/intrusive_collections/rbtree/struct.RBTree.html#method.upper_bound">https://docs.rs/intrusive-collections/0.8.5/intrusive_collections/rbtree/struct.RBTree.html#method.upper_bound</a></p>



<a name="191368147"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%20%22highest%20key%20below%22%20and%20ranges%20%22containing%22%20a%20key%3F/near/191368147" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.20.22highest.20key.20below.22.20and.20ranges.20.22containing.22.20a.20key.3F.html#191368147">(Mar 21 2020 at 22:16)</a>:</h4>
<p>Nice! That would indeed be perfect.</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>